﻿//天下第一
//https://www.luogu.com.cn/problem/P5635

//#include <iostream>
//
//using namespace std;
//
//const int N = 1e4 + 10;
//
//int x, y, p;
//
//char f[N][N];
//
//char dfs(int x, int y)
//{
//	if (f[x][y])
//		return f[x][y];
//
//	f[x][y] = '3';
//
//	if (x == 0)
//		return f[x][y] = '1';
//	if (y == 0)
//		return f[x][y] = '2';
//
//	//return f[x][y] = dfs((x + y) % p, (x + y + y) % p);
//	return f[x][y] = dfs((x + y) % p, (x + y + y) % p);
//}
//
//int main()
//{
//	int T;
//	cin >> T >> p;
//	while (T--)
//	{
//		cin >> x >> y;
//		char ret = dfs(x, y);
//		if (ret == '1')
//		{
//			cout << 1 << endl;
//		}
//		else if (ret == '2')
//		{
//			cout << 2 << endl;
//		}
//		else
//		{
//			cout << "error" << endl;
//		}
//	}
//
//	return 0;
//}


//#include <iostream>
//using namespace std;
//const int N = 1e4 + 10;
//int x, y, p;
//char f[N][N]; // 备忘录 
//
//char dfs(int x, int y)
//{
//	if (f[x][y]) return f[x][y]; // 剪枝 
//	f[x][y] = '3'; // 这个状态已经访问过了，之后再遇到时，表⽰平局 
//	if (x == 0) return f[x][y] = '1';
//	if (y == 0) return f[x][y] = '2';
//	return f[x][y] = dfs((x + y) % p, (x + y + y) % p);
//}
//
//int main()
//{
//	int T; cin >> T >> p;
//	while (T--)
//	{
//		cin >> x >> y;
//		char ret = dfs(x, y);
//		if (ret == '1') cout << 1 << endl;
//		else if (ret == '2') cout << 2 << endl;
//		else cout << "error" << endl;
//	}
//
//	return 0;
//}

//滑雪
//https://www.luogu.com.cn/problem/P1434

//#include <iostream>
//
//using namespace std;
//
//const int N = 120;
//int a[N][N];
//int f[N][N];
//
//int dx[] = { 0,0,1,-1 };
//int dy[] = { 1,-1,0,0 };
//
//int m, n;
//
//int dfs(int i, int j)
//{
//	if (f[i][j])
//		return f[i][j];
//
//	int len = 1;
//
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k], y = j + dy[k];
//		if (x < 1 || x > m || y < 1 || y > n) continue;
//		if (a[i][j] <= a[x][y]) continue;
//
//		len = max(dfs(x, y) + 1, len);
//	}
//
//	return f[i][j] = len;
//}
//
//int main()
//{
//	int ret = 1;
//	cin >> m >> n;
//
//	for (int i = 1; i <= m; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//
//	for (int i = 1; i <= m; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			ret = max(ret, dfs(i, j));
//		}
//	} 
//
//	cout << ret << endl;
//	return 0;
//}


//#include <iostream>
//#include <queue>
//using namespace std;
//
//typedef pair<int, int> PII;
//
//const int N = 410;
//
//int dist[N][N];
//int n, m, x, y;
//
//int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
//
//void bfs()
//{
//	memset(dist, -1, sizeof(dist));
//
//	queue<PII> q;
//	q.push({ x, y });
//	dist[x][y] = 0;
//
//	while (q.size())
//	{
//		auto t = q.front(); q.pop();
//
//		int i = t.first; 
//		int j = t.second;
//		for (int k = 0; k < 8; k++)
//		{
//			int x = i + dx[k];
//			int y = j + dy[k];
//			if (x < 1 || x > n || y < 1 || y > m) continue;
//			if (dist[x][y] != -1) continue;
//
//			dist[x][y] = dist[i][j] + 1; 
//			q.push({ x, y });
//		}
//	}
//}
//
//int main()
//{
//	cin >> n >> m >> x >> y;
//
//	bfs();
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cout << dist[i][j] << " ";
//		}
//		cout << endl;
//	}
//
//	return 0;
//}


//#include <iostream>
//#include <queue>
//#include <cstring>
//
//using namespace std;
//
//typedef pair<int, int> PII;
//
//const int N = 35;
//
//char a[N][N];
//int dist[N][N];
//
//int dx[] = { 0, 0, 1, -1 };
//int dy[] = { 1, -1, 0, 0 };
//
//int n, m, x, y;
//
//void bfs()
//{
//	memset(dist, -1, sizeof(dist));
//
//	queue<PII> q;
//	q.push({x, y}); 
//	dist[x][y] = 0;
//
//	while (q.size())
//	{
//		auto t = q.front(); q.pop();
//		int i = t.first;
//		int j = t.second;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k];
//			int y = j + dy[k];
//
//			if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '*' && dist[x][y] == -1)
//			{
//				dist[x][y] = dist[i][j] + 1;
//
//				if (a[x][y] == 'e')
//				{
//					continue;
//				}
//				q.push({ x, y });
//			}
//		}
//	}
//}
//
//int main()
//{
//	int ret = 1e9, cnt = 0;
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//			if (a[i][j] == 'k')
//				x = i, y = j;
//		}
//	}
//
//	bfs();
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (a[i][j] == 'e' && dist[i][j] != -1)
//			{
//				ret = min(ret, dist[i][j]);
//				cnt++;
//			}
//		}
//	}
//
//	if (cnt != 0)
//	{
//		cout << cnt << " " << ret;
//	}
//	else
//	{
//		cout << -1;
//	}
//
//	return 0;
//}


//#include <iostream>
//#include <queue>
//#include <cstring>
//
//using namespace std;
//
//const int N = 1e5 + 10;
//int n = 1e5;
//
//int dist[N];
//
//int x, y;
//
//void bfs()
//{
//	queue<int> q;
//	q.push(x);
//	dist[x] = 0;
//
//	while (q.size())
//	{
//		int t = q.front(); q.pop();
//
//		int a = t + 1;
//		int b = t - 1;
//		int c = t * 2;
//
//		if (a <= n && dist[a] == -1)
//		{
//			dist[a] = dist[t] + 1;
//			q.push(a);
//		}
//
//		if (b > 0 && dist[b] == -1)
//		{
//			dist[b] = dist[t] + 1;
//			q.push(b);
//		}
//
//		if (c <= n && dist[c] == -1)
//		{
//			dist[c] = dist[t] + 1;
//			q.push(c);
//		}
//
//		if (a == y || b == y || c == y)
//		{
//			return;
//		}
//	}
//
//}
//
//int main()
//{
//	int t;
//	cin >> t;
//	
//	while (t--)
//	{
//		memset(dist, -1, sizeof(dist));
//		cin >> x >> y;
//
//		bfs();
//
//		cout << dist[y];
//	}
//
//	return 0;
//}

//#include <iostream>
//#include <queue>
//#include <cstring>
//
//using namespace std;
//
//const int N = 1e5;
//
//int dist[N];
//
//int x, y;
//
//void bfs()
//{
//	queue<int> q;
//	q.push(x);
//	dist[x] = 0;
//
//	while (q.size())
//	{
//		auto t = q.front(); q.pop();
//		int a = t + 1;
//		int b = t - 1;
//		int c = t * 2;
//		if (a <= 1e5 && dist[a] == -1)
//		{
//			dist[a] = dist[t] + 1;
//			q.push(a);
//		}
//
//		if (b > 0 && dist[b] == -1)
//		{
//			dist[b] = dist[t] + 1;
//			q.push(b);
//		}
//
//		if (c <= 1e5 && dist[c] == -1)
//		{
//			dist[c] = dist[t] + 1;
//			q.push(c);
//		}
//
//		if (a == y || b == y || c == y)
//			return;
//	}
//}
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		memset(dist, -1, sizeof(dist));
//		cin >> x >> y;
//		bfs();
//		cout << dist[y];
//	}
//
//	return 0;
//}


//#include <iostream>
//#include <queue>
//#include <cstring>
//
//using namespace std;
//
//typedef pair<int, int> PII;
//
//const int N = 1010;
//
//int n, m;
//char a[N][N];
//int dist[N][N];
//
//int dx[] = { 0, 0, 1, -1 };
//int dy[] = { 1, -1, 0, 0 };
//
//void bfs()
//{
//	memset(dist, -1, sizeof(dist));
//	queue<PII> q;
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (a[i][j] == '1')
//			{
//				q.push({ i, j });
//				dist[i][j] = 0;
//			}
//		}
//	}
//
//	while (q.size())
//	{
//		auto t = q.front(); q.pop();
//		int x = t.first;
//		int y = t.second;
//
//		for (int k = 0; k < 4; k++)
//		{
//			int a = x + dx[k];
//			int b = y + dy[k];
//
//			if (a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1)
//			{
//				dist[a][b] = dist[x][y] + 1;
//				q.push({ a, b });
//			}
//		}
//	}
//}
//
//int main()
//{
//	cin >> n >> m;
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//
//	bfs();
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cout << dist[i][j] << " ";
//		}
//		cout << endl;
//	}
//
//	return 0;
//}

//#include <iostream>
//#include <queue>
//using namespace std;
//
//using namespace std;
//
//const int N = 110;
//
//int n, m;
//char a[N][N];
//bool st[N][N];
//
//int dx[] = { 0,0,1,-1,1,-1,-1,1 };
//int dy[] = { 1,-1,0,0,1,1,-1,-1 };
//
//void dfs(int i, int j) 
//{
//	st[i][j] = true;
//
//	for (int k = 0; k < 8; k++)
//	{
//		int x = i + dx[k];
//		int y = j + dy[k];
//
//		if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == 'W' && st[x][y] == false)
//		{
//			dfs(x, y);
//		}
//	}
//}
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (a[i][j] == 'W' && st[i][j] == false)
//			{
//				ret++;
//				dfs(i, j);
//			}
//		}
//	}
//	
//	cout << ret << endl;
//
//	return 0;
//}


